package cn.lishiyuan.leetcode;

import cn.lishiyuan.algorithm.stack.LeeStack;


/**
 * 在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
 * (1) 每次只能移动一个盘子;
 * (2) 盘子只能从柱子顶端滑出移到下一根柱子;
 * (3) 盘子只能叠在比它大的盘子上。
 *
 * 请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
 *
 * 你需要原地修改栈。
 *
 * 示例 1：
 *
 *  输入：A = [2, 1, 0], B = [], C = []
 *  输出：C = [2, 1, 0]
 * 示例 2：
 *
 *  输入：A = [1, 0], B = [], C = []
 *  输出：C = [1, 0]
 */
public class TowerOfHanoi {


    public void move(LeeStack<Integer> start,int startSize, LeeStack<Integer> temp , LeeStack<Integer> target){
        if(startSize == 1){
            Integer peek = start.peek();
            target.push(start.pop());
            System.out.println("将元素"+ peek +"从"+start+"移动到"+target);
            return;
        }

        startSize = startSize - 1;

        // 先将N-1个元素从start移动到temp
        move(start, startSize , target,temp);
        // 移动完成后将底部元素从start移动到target
        Integer peek = start.peek();
        target.push(start.pop());
        System.out.println("将元素"+ peek +"从"+start+"移动到"+target);
        // 再将N-1个元素从temp移动到target
        move(temp, startSize , start, target);
    }

}
